package codeRandomThoughts.Test51N皇后;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        backtracking(n, 0);
        List<List<String>> formatRes = new ArrayList<>();

        for (List<Integer> integers : result) {
            List<String> formatInt = new ArrayList<>();
            for (Integer integer : integers) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    if (i != integer) {
                        sb.append(".");
                    } else {
                        sb.append("Q");
                    }
                }
                formatInt.add(new String(sb));
            }
            formatRes.add(formatInt);
        }
        return formatRes;
    }

    public void backtracking(int n, int row) {
        //终止条件
        if (path.size() == n) {
            result.add(new ArrayList<>(path));
            return;
        }

        //单层搜索逻辑
        for (int i = 0; i < n; i++) {
            if (isValid(row, i)) {
                path.add(i);
                backtracking(n, row + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    boolean isValid(int row, int column) {
        for (int i = 0; i < path.size(); i++) {
            //皇后所在的横纵坐标 横坐标是i 纵坐标是path.get(i)
            if (column == path.get(i) || (Math.abs(column - path.get(i)) == Math.abs(row - i))) {
                return false;
            }
        }
        return true;
    }
}
